package com.mjlf.algorithms.sort;

/**
 * @auther a123
 * @create 2018-09-08 10:04
 * @desc 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
//        Comparable[] elements = new Comparable[]{"4PGC938",
//        "2IYE230",
//        "3CIO720",
//        "1ICK750",
//        "10HV845",
//        "4JZY524",
//        "1ICK750",
//        "3CIO720",
//        "1OHV845",
//        "1OHV845",
//        "2RLA629",
//        "2RLA629",
//        "3ATW723"};

        Comparable[] elements = new Comparable[]{1, 1, 2, 1};

        sort(elements);



        SortUtil.show(elements);
    }

    public static void sort(Comparable[] elements){
        sort(elements, 0, elements.length - 1);
    }

    public static void sort(Comparable[] elements, int lo, int hi){
        if(lo >= hi){
            return;
        }
        int index = partition(elements, lo, hi);
        sort(elements, lo, index -1);
        sort(elements, index + 1, hi);
    }


    /**
     * 找到原始的合适位置， 要做该位置左边的原始都小于它， 右边的元素都大于它
     *
     * 千万不要进入误区，要求左边的每一个元素都大于其左边的元素， 这样就已经排好序了
     *
     * @param elements
     * @param lo
     * @param hi
     *
     * @return
     */
    public static int partition(Comparable[] elements, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while(i < j){
            while(SortUtil.less(elements[++i], elements[lo])){
                if(i >= hi){
                    break;
                }
            }
            while(SortUtil.less(elements[lo],elements[--j])){
                if(j <= lo){
                    break;
                }
            }
            if(i >= j){
                break;
            }
            SortUtil.exch(elements, i, j);
        }
        SortUtil.exch(elements, lo, j);

        //j 后边的元素都大于j对应元素，
        return j;
    }
}
